package main

import (
	"fmt"
	"math/rand"
	"time"
)

/* 水塘抽样 */

func main() {
	s := []int{1, 2, 3, 4, 5, 65, 67, 78, 8, 8, 766, 9, 678, 676, 6547654, 65}
	k := 6
	fmt.Println(ReserviorSampling(s, k))
}

// 从stream的水塘中抽取k个
func ReserviorSampling(stream []int, k int) []int {
	// var res = make([]int,0, k)
	var res = make([]int, k)
	copy(res, stream[:k]) // 从水塘中取出k个数字
	rand.Seed(time.Now().UnixNano())

	// 迭代遍历k+1之后的值
	// 随机生成一个 [0,k+i] 中间的值，如果这个值在[0,k]中，
	// 则将stream[k+i]的值捕获
	for i := k; i < len(stream); i++ {
		x := rand.Intn(i + 1)
		if x < k {
			res[x] = stream[i]
		}
	}
	return res
}

// 因为水塘抽样已经从数学理论上证明了每一个值从项目流中被抽中的概率是相等的。
